#include<string>
#include<vector>
#include<array>
#include<unordered_map>
class Solution {
public:
    int trap(std::vector<int>& height) {
        int n = height.size();
        if (n<3) return 0;
        int lmax = height[0];
        int l = 1;
        int r = n-2;
        int rmax = height[n-1];
        int ans = 0;
        while (l<=r)
        {
            if (lmax<=rmax)
            {
                ans += std::max(lmax - height[l],0);
                lmax = std::max(lmax, height[l]);
                l++;
            }
            else
            {
                ans+=std::max(rmax - height[r],0);
                rmax = std::max(rmax, height[r]);
                r--;
            }
        }
        return ans ; 
    }
};
